class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        if not s or not t:
            return 0
        DP = [[0 for _ in range(len(s))] for _ in range(len(t))]
        for i in range(len(t)):
            for j in range(i, len(s)):
                if s[j] == t[i]:
                    if j == 0:
                        DP[i][j] = 1
                    else:
                        if i == 0:
                            DP[i][j] = DP[i][j - 1] + 1
                        else:
                            DP[i][j] = DP[i][j - 1] + DP[i - 1][j - 1]
                else:
                    if j > 0:
                        DP[i][j] = DP[i][j - 1]
        return DP[len(t) - 1][len(s) - 1]

data = Solution()
s = "babgbag"
t = "bag"
print(data.numDistinct(s, t))